package com.example.graph;

import java.util.*;

/**
 * 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，
 * 其中 equations[i] = [Ai, Bi] 和values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
 * 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj =? 的结果作为答案。
 * 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
 * <p>
 * 注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
 * <p>
 * 示例 1：
 * 输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
 * 输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
 * 解释：
 * 条件：a / b = 2.0, b / c = 3.0
 * 问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
 * 结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
 * <p>
 * 示例 2：
 * 输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
 * 输出：[3.75000,0.40000,5.00000,0.20000]
 * <p>
 * 示例 3：
 * 输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
 * 输出：[0.50000,2.00000,-1.00000,-1.00000]
 * <p>
 * 提示：
 * 1 <= equations.length <= 20
 * equations[i].length == 2
 * 1 <= Ai.length, Bi.length <= 5
 * values.length == equations.length
 * 0.0 < values[i] <= 20.0
 * 1 <= queries.length <= 20
 * queries[i].length == 2
 * 1 <= Cj.length, Dj.length <= 5
 * Ai, Bi, Cj, Dj 由小写英文字母与数字组成
 * <p>
 * Related Topics 深度优先搜索 广度优先搜索 并查集 图 数组 最短路
 */
public class Leetcode399_CalcEquation {
    public static void main(String[] args) {
        List<List<String>> equations;
        double[] values;
        List<List<String>> queries;
        // equations = [["a","b"],["b","c"]]
        equations = new ArrayList<>();
//        List<String> equation1 = new ArrayList<>();
//        equation1.add("a");
//        equation1.add("b");
//        List<String> equation2 = new ArrayList<>();
//        equation2.add("b");
//        equation2.add("c");
//        equations.add(equation1);
//        equations.add(equation2);
//
//        // values = [2.0,3.0]
//        values = new double[]{2.0, 3.0};
//
//        //  queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
//        queries = new ArrayList<>();
//        List<String> query1 = new ArrayList<>();
//        query1.add("a");
//        query1.add("c");
//        List<String> query2 = new ArrayList<>();
//        query2.add("b");
//        query2.add("a");
//        List<String> query3 = new ArrayList<>();
//        query3.add("a");
//        query3.add("e");
//        List<String> query4 = new ArrayList<>();
//        query4.add("a");
//        query4.add("a");
//        List<String> query5 = new ArrayList<>();
//        query5.add("x");
//        query5.add("x");
//        queries.add(query1);
//        queries.add(query2);
//        queries.add(query3);
//        queries.add(query4);
//        queries.add(query5);

        // [["x1","x2"],["x2","x3"],["x3","x4"],["x4","x5"]]   [3.0,4.0,5.0,6.0]
        // [["x1","x5"],["x5","x2"],["x2","x4"],["x2","x2"],["x2","x9"],["x9","x9"]]
        List<String> equation1 = new ArrayList<>();
        equation1.add("x1");
        equation1.add("x2");
        List<String> equation2 = new ArrayList<>();
        equation2.add("x2");
        equation2.add("x3");
        List<String> equation3 = new ArrayList<>();
        equation3.add("x3");
        equation3.add("x4");
        List<String> equation4 = new ArrayList<>();
        equation4.add("x4");
        equation4.add("x5");
        equations.add(equation1);
        equations.add(equation2);
        equations.add(equation3);
        equations.add(equation4);

        values = new double[]{3.0, 4.0, 5.0, 6.0};

        queries = new ArrayList<>();
        List<String> query1 = new ArrayList<>();
        query1.add("x1");
        query1.add("x5");
        List<String> query2 = new ArrayList<>();
        query2.add("x5");
        query2.add("x2");
        List<String> query3 = new ArrayList<>();
        query3.add("x2");
        query3.add("x4");
        List<String> query4 = new ArrayList<>();
        query4.add("x2");
        query4.add("x2");
        List<String> query5 = new ArrayList<>();
        query5.add("x2");
        query5.add("x9");
        List<String> query6 = new ArrayList<>();
        query6.add("x9");
        query6.add("x9");
        queries.add(query1);
        queries.add(query2);
        queries.add(query3);
        queries.add(query4);
        queries.add(query5);
        queries.add(query6);

        // 期望结果:[360.0,0.00833,20.0,1.0,-1.0,-1.0]
        double[] res = new Solution().calcEquation(equations, values, queries);


        for (double re : res) {
            System.out.print(re + ", ");
        }
    }

    static class Solution {
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            return calcEquation2(equations, values, queries);
        }

        /**
         * 并查集
         * @param equations
         * @param values
         * @param queries
         * @return
         */
        public double[] calcEquation2(List<List<String>> equations, double[] values, List<List<String>> queries) {
            int equationsSize = equations.size();

            /**
             * 第 1 步：预处理，将变量的值与 id 进行映射，使得并查集的底层使用数组实现，方便编码
             * 每个不同的变量都被映射成了不同的id值
             */
            Map<String, Integer> map = new HashMap<>(2 * equationsSize); // 有可能equations集合中每个数据对都不相同
            UnionFindSet unionFind = new UnionFindSet(2 * equationsSize);
            int id = 0;
            for (int i = 0; i < equationsSize; i++) {
                List<String> equation = equations.get(i);
                String var1 = equation.get(0);
                String var2 = equation.get(1);

                if (!map.containsKey(var1)) {
                    map.put(var1, id);
                    id++;
                }
                if (!map.containsKey(var2)) {
                    map.put(var2, id);
                    id++;
                }
                unionFind.union(map.get(var1), map.get(var2), values[i]);
            }

            // 第 2 步：做查询
            int queriesSize = queries.size();
            double[] res = new double[queriesSize];
            for (int i = 0; i < queriesSize; i++) {
                String var1 = queries.get(i).get(0);
                String var2 = queries.get(i).get(1);

                Integer id1 = map.get(var1);
                Integer id2 = map.get(var2);

                if (id1 == null || id2 == null) { // 其中一个变量不在
                    res[i] = -1.0;
                } else {
                    res[i] = unionFind.isConnected(id1, id2);
                }
            }
            return res;
        }


        /**
         * 解法一:DFS遍历
         * 先根据 equations 和 values两个数组构建一个有向图(邻接表)
         * a / b = 2.0 表示a->b有向边为2.0;b->a有向边为0.5
         * 然后DFS遍历 queries 中提供的每个query
         *     判断两个query.get(0)和query.get(1)是否连通并求解
         *
         * @param equations
         * @param values
         * @param queries
         * @return
         */
        public double[] calcEquation1(List<List<String>> equations, double[] values, List<List<String>> queries) {
            double[] res = new double[queries.size()];
//            Arrays.fill(res, -1.0);
            Map<String, Map<String, Double>> adj;// key为from顶点, value.key为to顶点,value.value为两点的商

            adj = makeAdj(equations, values);

            int i = 0;
            for (List<String> query : queries) {
                String dividend = query.get(0); // 被除数
                String divisor = query.get(1); // 除数
                System.out.println(dividend + "  " + divisor);
                res[i++] = dfs(adj, dividend, divisor, new HashSet<>(), 1.0);
            }

            return res;

        }

        private class UnionFindSet {

            private int[] parent;

            /**
             * 指向的父结点的权值(是于父节点的几倍 ) weight[i] = m 代表: i节点是其父节点(代表节点)的m倍
             */
            private double[] weight;


            public UnionFindSet(int n) {
                this.parent = new int[n];
                this.weight = new double[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                    weight[i] = 1.0d;
                }
            }

            public void union(int x, int y, double value) {
                int rootX = find(x);
                int rootY = find(y);
                if (rootX == rootY) {
                    return;
                }

                parent[rootX] = rootY;
                weight[rootX] = weight[y] * value / weight[x];
            }

            /**
             * 路径压缩 + 计算更新倍数关系
             *
             * @param x
             * @return 根结点的 id
             */
            public int find(int x) {
                if (x != parent[x]) {
                    int origin = parent[x];
                    parent[x] = find(parent[x]);
                    weight[x] *= weight[origin];
                }
                return parent[x];
            }

            /**
             * 判断两个点是否连通
             * @param x
             * @param y
             * @return 连通的话返回两者的倍数关系，不连通返回-1.0
             */
            public double isConnected(int x, int y) {
                int rootX = find(x);
                int rootY = find(y);
                if (rootX == rootY) {
                    return weight[x] / weight[y];
                } else {
                    return -1.0;
                }
            }
        }

        /**
         *
         * @param adj
         * @param node1 被除数变量
         * @param node2 除数变量
         * @param visited 节点是否被访问过
         * @param res
         * @return
         */
        private double dfs(Map<String, Map<String, Double>> adj, String node1, String node2,
                           Set<String> visited, double res) {
            // 首先看看图中有没有被除数这个根节点,或者被除数下面没有可连通的元素
            // 或者被除数 或者 除数 不存在，直接返回-1.0
            if (adj.get(node1) == null || adj.get(node1).size() == 0 ||
                    !adj.keySet().contains(node1) || !adj.keySet().contains(node2)) {
                return -1;
            }
            // 如果有dividend且dividend和divisor直接相连
            if (adj.get(node1).containsKey(node2)) {
                return res * adj.get(node1).get(node2);
            }

            visited.add(node1); // 将遍历了的点置为已访问,避免有环进入无限递归导致stackoverflow

            // 如果有dividend且dividend和divisor不是直接相连的
            if (!adj.get(node1).containsKey(node2)) {
                for (String next : adj.get(node1).keySet()) {
                    if (!visited.contains(next)) {
                        double tmp = dfs(adj, next, node2, visited, adj.get(node1).get(next) * res);
                        if (tmp != -1) { // 如果搜到了答案，就直接返回答案
                            return tmp;
                        }
                    }

                }
            }

            // 两点不连通，无法求值，返回-1.0
            return -1.0;
        }

        private Map<String, Map<String, Double>> makeAdj(List<List<String>> equations, double[] values) {
            Map<String, Map<String, Double>> adj = new HashMap<>();

            for (int i = 0; i < values.length; i++) {
                String from = equations.get(i).get(0);
                String to = equations.get(i).get(1);
                // 分别添加 from -> to 的边和 to -> from的边
                adj.computeIfAbsent(from, key -> new HashMap<>()).put(to, values[i]);
                adj.computeIfAbsent(to, key -> new HashMap<>()).put(from, 1.0 / values[i]);
                // 添加两个顶点自己到自己的边
                adj.computeIfAbsent(from, key -> new HashMap<>()).put(from, 1.0);
                adj.computeIfAbsent(to, key -> new HashMap<>()).put(to, 1.0);
            }

            return adj;
        }
    }
}
